package com.ryujung.binary_tree.leetCode_110;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val + (left == null && right == null ? "" :
                (left == null ? "," : ",\n") + " left=" + left +
                        (right == null ? "," : ",\n") + " right=" + right +
                        '}');
    }
}

class Solution {
    /**
     * 本题中，一棵高度平衡二叉树定义为：
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     * <p>
     * 尝试自底向上的递归方式
     *
     * 时间复杂度：O(n)，其中 n 是二叉树中的节点个数。
     * 使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，
     * 最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。
     *
     * 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。
     * 空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。
     */
    public boolean isBalanced2(TreeNode root) {
        if (root == null) return true;

        return height2(root) >= 0;
    }

    private int height2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height2(root.left);
        int rightHeight = height2(root.right);

        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
    // 时间复杂度：O(n)
    // 空间复杂度：O(n)


    /**
     * 本题中，一棵高度平衡二叉树定义为：
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int height(TreeNode root) {
        if (root == null) return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    /*
     * 时间复杂度：O(n^2)，其中 n 是二叉树中的节点个数。
     * 最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)。
     * 对于节点 p，如果它的高度是 d，则 height(p) 最多会被调用 d 次（即遍历到它的每一个祖先节点时）。
     * 对于平均的情况，一棵树的高度 h 满足O(h)=O(logn)，因为 d≤h，所以总时间复杂度为O(nlogn)。
     * 对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2)。
     *
     * 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。
     */

    /*
     * 一下均为错误解答，
     * 总结错误原因，对题目中的平衡二叉树理解不正确，
     * [1,2,2,3,3,3,3,4,4,4,4,4,4,null,null,5,5] 是一颗符合题意的平衡二叉树，
     * 但是理解有误，认为这不是平衡二叉树，进而将过程复杂化，导致无法通过
     */


    public static boolean isBalancedWrong1(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> que = new ArrayDeque<>();
        que.add(root);

        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();

                if (node.left != null) {
                    if (node.left.left != null || node.left.right != null) {
                        return false;
                    }
                    que.add(node.left);
                }
                if (node.right != null) {
                    if (node.right.left != null || node.right.right != null) {
                        return false;
                    }
                    que.add(node.right);
                }
            }
        }
        return true;
    }

    /**
     * 本题中，高度平衡二叉树
     */
    public static boolean isBalancedTree(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> que = new ArrayDeque<>();
        que.add(root);
        int curDepth = 0;
        boolean isFindMin = root.left == null || root.right == null;
        int minDepth = isFindMin ? 1 : 0;

        while (!que.isEmpty()) {
            int size = que.size();
            if (!isFindMin) {
                minDepth++;
            }
            curDepth++;
            if (curDepth - minDepth > 1) {
                return false;
            }
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if (!isBalancedTree(node)) {
                    return false;
                }
                if (node.left == null && node.right == null) {
                    isFindMin = true;
                }
                if (node.left != null) {
                    que.add(node.left);
                }
                if (node.right != null) {
                    que.add(node.right);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode node = newNode(new Integer[]{1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, null, null, 5, 5});
        System.out.println(node);
        System.out.println(isBalanced222(node));
    }

    public static TreeNode newNode(Integer[] nodeSeq) {
        if (nodeSeq == null || nodeSeq.length == 0) {
            return null;
        }

        Queue<TreeNode> que = new ArrayDeque<>();
        TreeNode root = new TreeNode(nodeSeq[0]);
        que.add(root);
        int j = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if (node != null) {
                    j++;
                    if (j < nodeSeq.length && nodeSeq[j] != null) {
                        int leftVal = nodeSeq[j];
                        TreeNode leftNode = new TreeNode(leftVal);
                        node.left = leftNode;
                        que.add(leftNode);
                    }
                    j++;
                    if (j < nodeSeq.length && nodeSeq[j] != null) {
                        int rightVal = nodeSeq[j];
                        TreeNode rightNode = new TreeNode(rightVal);
                        node.right = rightNode;
                        que.add(rightNode);
                    }
                }
            }
        }
        return root;
    }

    public static boolean isBalanced222(TreeNode root) {
        boolean result = true;
        Deque<TreeNode> stk = new LinkedList<>();
        while (root != null || !stk.isEmpty()) {
            if (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            result &= isBalancedHelper(root);
            root = root.right;
        }
        return result;
    }

    public static boolean isBalancedHelper(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> que = new ArrayDeque<>();
        que.add(root);
        int curDepth = 0;
        boolean isFindMin = root.left == null || root.right == null;
        int minDepth = isFindMin ? 1 : 0;

        while (!que.isEmpty()) {
            int size = que.size();
            if (!isFindMin) {
                minDepth++;
            }
            curDepth++;
            if (curDepth - minDepth > 1) {
                return false;
            }
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if (node.left == null && node.right == null) {
                    isFindMin = true;
                }
                if (node.left != null) {
                    que.add(node.left);
                }
                if (node.right != null) {
                    que.add(node.right);
                }
            }
        }
        return true;
    }

}